package com.example.spring;

import java.util.Stack;

public class QueueWithTwoStacks {
    private Stack<Integer> stack1; // 用于入队操作
    private Stack<Integer> stack2; // 用于出队操作

    public QueueWithTwoStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // 入队操作
    public void enqueue(int item) {
        stack1.push(item);
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }

        // 如果stack2为空，将stack1的所有元素转移到stack2
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        return stack2.pop();
    }

    // 查看队首元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }

        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        return stack2.peek();
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    // 获取队列大小
    public int size() {
        return stack1.size() + stack2.size();
    }

    public static void main(String[] args) {
        QueueWithTwoStacks queue = new QueueWithTwoStacks();

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println(queue.dequeue()); // 输出1
        System.out.println(queue.peek());    // 输出2
        queue.enqueue(4);
        System.out.println(queue.dequeue()); // 输出2
        System.out.println(queue.dequeue()); // 输出3
        System.out.println(queue.dequeue()); // 输出4
        System.out.println(queue.isEmpty()); // 输出true
    }
}
